package 力扣.树.层序遍历;

import java.util.LinkedList;
import java.util.Queue;
class Pair {//创建一个新对象来保存数据：节点及其位置
    public TreeNode node;
    public int id;//位置
    public Pair(TreeNode n, int i) {
        node = n;
        id = i;
    }
}
public class 二叉树的最大宽度662 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);

        TreeNode root21 = new TreeNode(9);
        TreeNode root22 = new TreeNode(20);

        TreeNode root31 = new TreeNode(15);
        TreeNode root32 = new TreeNode(7);

        root.left = root21;
        root.right = root22;
        root22.left = root31;
        root22.right = root32;

        int i = widthOfBinaryTree(root);
        System.out.println(i);
    }

    /**每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
     * 属于是满二叉树的变种，我们需要知道左边非空节点和右边非空节点所在的位置信息，才能计算长度。
     *    左子结点位置为 2 * x
     *    右子结点位置为 2 * x + 1
     * @param root
     * @return
     */
    public static int widthOfBinaryTree(TreeNode root) {
            // 生成FIFO队列
            Queue<Pair> Q = new LinkedList<>();

            // 如果结点不为空，那么加入到FIFO队列
            if (root != null) {
                Q.offer(new Pair(root, 0));
            }

            int ans = 0;

            // 开始利用FIFO队列进行层次遍历
            while (Q.size() > 0) {
                // 取出当前层里面元素的个数
                final int qSize = Q.size();
                int start = -1;
                int end = -1;
                // 这里要在当前层中找到[start, end]
                // 在这个区间之外的都是null
                // 这些null的子结点是不能入队的。
                // 但是在[start, end]这个范围里面的null
                // 是可以入队的。
                for (int i = 0; i < qSize; i++) {
                    // 当前层前面的结点先出队
                    Pair cur = Q.poll();
                    if (-1 == start) {
                        start = cur.id;
                    }
                    end = cur.id;
                    if (cur.node.left != null) {
                        Q.offer(new Pair(cur.node.left, cur.id << 1));//乘以2
                    }
                    if (cur.node.right != null) {
                        Q.offer(new Pair(cur.node.right, (cur.id<<1) + 1));//乘以2 + 1
                    }
                }
                ans = Math.max(ans, end - start + 1);
            }

            return ans;
    }

//定义结构体保存二叉树节点、编号
    public int widthOfBinaryTree2(TreeNode root) {
        Queue<Pair> queue = new LinkedList<>();
         if (root != null){
             queue.add(new Pair(root, 1));
         }
         int ans = 0;
         while(!queue.isEmpty()){
             int size = queue.size();
             int first = 0;
             int last = 0;
             while(size-- >0){
                 Pair te = queue.poll();
                 if (first == 0){
                     first = te.id;
                 }
                 last = te.id;
                 if (te.node.left != null){
                     queue.add(new Pair(te.node.left,te.id * 2));
                 }
                 if (te.node.right != null){
                     queue.add(new Pair(te.node.right, te.id * 2 + 1));
                 }
             }
             ans = Math.max(ans, last - first + 1);
         }
         return ans;
    }
}
